/* 图采用邻接表存储，设计算法判断i和j结点之间是否有路径(以下全是邻接表存储) */

#include <iostream>
#include "algraph.h"
using namespace std;

// 深度优先搜索
void DFS(ALGraph *G, int v, int visit[])
{
  // 访问开始结点
  visit[v] = 1;
  
  // 找到开始结点的邻接结点
  ArcNode *p = G->adjlist[v].firstarc;
  
  // 如果邻接结点不为空
  while (p != NULL)
  {
    // 邻接结点未被访问
    if (visit[p->adjvex] == 0)
      DFS(G, p->adjvex, visit); // 从邻接结点开始，深度优先遍历
    
    // 到下一个邻接结点
    p = p->nextarc;
  }
}

// 深度优先搜索，判断两点之间是否存在路径
bool DFS1(ALGraph *G, int i, int j)
{
  int k;
  
  // 标记各个结点是否被访问
  int visit[maxsize];
  
  // 初始时，结点均未被访问
  for (k = 0; k < G->numver; ++k)
    visit[k] = 0;
  
  // 深度优先搜索
  DFS(G, i, visit);
  
  // 判断j是否被访问
  if (visit[j] == 1)
    return true;
  else
    return false;
}
int main()
{
  ALGraph *G = create_algraph(4, 3);
  
  // 深度优先搜索，找路径
  if (DFS1(G, 0, 2))
    cout << "路径存在！";
  else
    cout << "路径不存在！";
  return 0;
}